package question.solution87;

import question.SolutionTemplate;

import java.util.HashMap;
import java.util.Map;

public class Solution87 implements SolutionTemplate {

    public boolean isScramble(String s1, String s2) {
        return isScramble2(s1, s2);
    }

    private boolean isScramble1(String s1, String s2){
        if(s1.length() != s2.length()){
            return false;
        }
        char[] charArr1 = s1.toCharArray();
        char[] charArr2 = s2.toCharArray();
        return isScramble(charArr1, charArr2, 0, charArr1.length-1, 0, charArr2.length-1);
    }

    private boolean isScramble(char[] s1, char[] s2, int s1BeginIndex, int s1EndIndex, int s2BeginIndex, int s2EndIndex){
        boolean qualified = true;
        for(int i=0;i<=s1EndIndex-s1BeginIndex;i++){
            if(s1[s1BeginIndex + i] != s2[s2BeginIndex + i]){
                qualified = false;
                break;
            }
        }
        if(qualified){
            return true;
        }
        for(int i=0;i<s1EndIndex - s1BeginIndex;i++){
            if(isScramble(s1, s2, s1BeginIndex, s1BeginIndex+i,s2BeginIndex, s2BeginIndex+i) &&
                isScramble(s1, s2, s1BeginIndex+i+1, s1EndIndex,s2BeginIndex+i+1, s2EndIndex)){
                return true;
            }
            if(isScramble(s1, s2, s1BeginIndex, s1BeginIndex+i,s2EndIndex-i, s2EndIndex) &&
                    isScramble(s1, s2, s1BeginIndex+i+1, s1EndIndex,s2BeginIndex, s2EndIndex-i-1)){
                return true;
            }
        }
        return false;
    }

    private boolean isScramble2(String s1, String s2){
        if(s1.length() != s2.length()){
            return false;
        }
        char[] charArr1 = s1.toCharArray();
        char[] charArr2 = s2.toCharArray();
        int n = charArr1.length;
        boolean[][][] dp = new boolean[n][n][n+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j][1] = charArr1[i] == charArr2[j];
            }
        }

        // 枚举区间长度 2～n
        for (int len = 2; len <= n; len++) {
            // 枚举 S 中的起点位置
            for (int i = 0; i <= n - len; i++) {
                // 枚举 T 中的起点位置
                for (int j = 0; j <= n - len; j++) {
                    // 枚举划分位置
                    for (int k = 1; k <= len - 1; k++) {
                        // 第一种情况：S1 -> T1, S2 -> T2
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        // 第二种情况：S1 -> T2, S2 -> T1
                        // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];

    }


    public void test() {
        String s1 = "ccabcbabcbabbbbcbb";
        String s2 = "bbbbabccccbbbabcba";
        boolean result = isScramble(s1, s2);
        return;
    }
}
